package listbyorder.access001_100.test99;

import listbyorder.utils.TreeNode;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/6 11:07
 */
public class Solution2 {

    // 方法二： 使用一个list存放中序遍历的结果，然后结果排序，然后再填入原来的树结构中
    public void recoverTree(TreeNode root) {
        List<Integer> data = new ArrayList<>();
        getData(root,data);
        data.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1.compareTo(o2);
            }
        });
        changeTree(root,data);
    }

    private void changeTree(TreeNode root, List<Integer> data) {
        TreeNode c1 = root;
        TreeNode c2 = null;
        while(c1 != null){
            c2 = c1.left;
            if(c2 != null){
                while(c2.right != null && c2.right != c1){
                    c2 = c2.right;
                }
                if(c2.right == null){
                    c2.right = c1;
                    c1 = c1.left;
                    continue;
                }
                if(c2.right == c1){
                    c2.right = null;
                }
            }
            c1.val = data.remove(0);
            c1 = c1.right;
        }
    }

    private void getData(TreeNode root, List<Integer> data) {
        TreeNode c1 = root;
        TreeNode c2 = null;
        while(c1 != null){
            c2 = c1.left;
            if(c2 != null){
                while(c2.right != null && c2.right != c1){
                    c2 = c2.right;
                }
                if(c2.right == null){
                    c2.right = c1;
                    c1 = c1.left;
                    continue;
                }
                if(c2.right == c1){
                    c2.right = null;
                }
            }
            data.add(c1.val);
            c1 = c1.right;
        }
    }
}
